[프로그래머스] 주식가격 (파이썬)

문제

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

입출력 예 설명

1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

풀이과정 & 완성코드

이 문제 역시 스택/큐를 활용할 풀이가 생각 안나서.. 완전탐색처럼 풀어봤는데 입력값이 크지 않아서 통과를 하긴 했다.

prices 리스트의 각 원소에 대해, 그 다음 값들을 쭉쭉 비교하면서 sec += 1 해주다가, 더 작은 값이 나오면 while 반복문 종료해준다.

여기서 헷갈렸던 점이 1초 뒤에 바로 가격이 떨어져도 1초동안은 가격이 떨어지지 않은 것으로 본다는 점이었다. 그래서 리스트의 끝까지 비교해서 while문이 종료된게 아니라, 뒤에 작은값이 나와서 while문이 끝난 경우, sec에 한번더 +=1 해주었다.

완성코드 :

def solution(prices):
    answer = []
    for i in range(len(prices)-1):
        j = i+1
        sec = 0  # 가격이 몇초간 떨어지지 않는지 담을 변수
        while j < len(prices) and prices[i] <= prices[j]:
            sec += 1
            j += 1
        if j != len(prices):
            sec += 1
        answer.append(sec)
    answer.append(0)  # 마지막 원소는 비교할 대상이 없으므로 무조건 0
    return answer

다른 풀이

위의 코드는 반복문을 2번 돌리기 때문에 O(n^2)이다. 더 효율적으로 풀 방법은 없을까?

from collections import deque

def solution(prices):
   answer = []
   prices = deque(prices)
   while prices:
       target = prices.popleft()  # 각 가격

       sec = 0  # 가격이 몇초간 떨어지지 않는지 담을 변수 
       for i in prices:
           if target > i:  # 현 가격보다 떨어진 가격이 있으면 break
               sec += 1  # 바로 떨어지면 1초동안 유지된 것으로 본다
               break
           sec += 1  

       answer.append(sec)

   return answer

큐를 사용해서 O(n)으로 풀 수 있었다.
리스트 내에 있는 첫 원소부터 순서대로 뭔가 계산/처리를 해봐야 하는 경우 큐를 사용해서 하나씩 없애가면서 풀어보면 될 것 같다… (라고 정답코드를 보고 나면 말할수야 있지만 떠올리기가 너무 어렵다구…)